package com.leetcode.algorithm.y19.m01;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

import com.leetcode.algorithm.common.TreeNode;

/**
 * leetcode-cn.com
 * (done)811. 子域名访问计数
 * (done)806. 写字符串需要的行数
 * (done)682. 棒球比赛
 * (done)575. 分糖果
 * @author: jie.deng
 * @time: 2019年1月26日 下午6:59:14
 */
public class MySolution0126 {

	/**
	 * 811. 子域名访问计数
	 * 
     * 一个网站域名，如"discuss.leetcode.com"，包含了多个子域名。作为顶级域名，常用的有"com"，下一级则有"leetcode.com"，最低的一级为"discuss.leetcode.com"。当我们访问域名"discuss.leetcode.com"时，也同时访问了其父域名"leetcode.com"以及顶级域名 "com"。
     * 
     * 给定一个带访问次数和域名的组合，要求分别计算每个域名被访问的次数。其格式为访问次数+空格+地址，例如："9001 discuss.leetcode.com"。
     * 
     * 接下来会给出一组访问次数和域名组合的列表cpdomains 。要求解析出所有域名的访问次数，输出格式和输入格式相同，不限定先后顺序。
     * 
     * 示例 1:
     * 输入: 
     * ["9001 discuss.leetcode.com"]
     * 输出: 
     * ["9001 discuss.leetcode.com", "9001 leetcode.com", "9001 com"]
     * 说明: 
     * 例子中仅包含一个网站域名："discuss.leetcode.com"。按照前文假设，子域名"leetcode.com"和"com"都会被访问，所以它们都被访问了9001次。
     * 示例 2
     * 输入: 
     * ["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
     * 输出: 
     * ["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]
     * 说明: 
     * 按照假设，会访问"google.mail.com" 900次，"yahoo.com" 50次，"intel.mail.com" 1次，"wiki.org" 5次。
     * 而对于父域名，会访问"mail.com" 900+1 = 901次，"com" 900 + 50 + 1 = 951次，和 "org" 5 次。
     * 注意事项：
     * 
     *  cpdomains 的长度小于 100。
     * 每个域名的长度小于100。
     * 每个域名地址包含一个或两个"."符号。
     * 输入中任意一个域名的访问次数都小于10000。
	 * @param cpdomains
	 * @return
	 */
	public List<String> subdomainVisits(String[] cpdomains) {
		Map<String, Integer> map = new HashMap<String, Integer>();
		for (String cpdomain : cpdomains) {
			String[] split = cpdomain.split(" ");
			int cp = Integer.parseInt(split[0]);
			String domain = split[1];
			
			map.put(domain, map.get(domain) == null ? cp : cp + map.get(domain));
			while (domain.indexOf(".") > 0) {
				domain = domain.substring(domain.indexOf(".") + 1);
				map.put(domain, map.get(domain) == null ? cp : cp + map.get(domain));
			}
		}
		List<String> retList = new ArrayList<String>();
		for (Map.Entry<String, Integer> entry : map.entrySet()) {
			retList.add(entry.getValue() + " " + entry.getKey());
		}
		return retList;
	}
    
    /**
     * 806. 写字符串需要的行数
     * 
     * 我们要把给定的字符串 S 从左到右写到每一行上，每一行的最大宽度为100个单位，如果我们在写某个字母的时候会使这行超过了100 个单位，那么我们应该把这个字母写到下一行。我们给定了一个数组 widths ，这个数组 widths[0] 代表 'a' 需要的单位， widths[1] 代表 'b' 需要的单位，...， widths[25] 代表 'z' 需要的单位。
     * 
     * 现在回答两个问题：至少多少行能放下S，以及最后一行使用的宽度是多少个单位？将你的答案作为长度为2的整数列表返回。
     * 
     * 示例 1:
     * 输入: 
     * widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
     * S = "abcdefghijklmnopqrstuvwxyz"
     * 输出: [3, 60]
     * 解释: 
     * 所有的字符拥有相同的占用单位10。所以书写所有的26个字母，
     * 我们需要2个整行和占用60个单位的一行。
     * 示例 2:
     * 输入: 
     * widths = [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
     * S = "bbbcccdddaaa"
     * 输出: [2, 4]
     * 解释: 
     * 除去字母'a'所有的字符都是相同的单位10，并且字符串 "bbbcccdddaa" 将会覆盖 9 * 10 + 2 * 4 = 98 个单位.
     * 最后一个字母 'a' 将会被写到第二行，因为第一行只剩下2个单位了。
     * 所以，这个答案是2行，第二行有4个单位宽度。
     *  
     * 
     * 注:
     * 
     * 字符串 S 的长度在 [1, 1000] 的范围。
     * S 只包含小写字母。
     * widths 是长度为 26的数组。
     * widths[i] 值的范围在 [2, 10]。
     * @param widths
     * @param S
     * @return
     */
	public int[] numberOfLines(int[] widths, String S) {
		int col = 0;
		int row = 1;
		char[] chars = S.toCharArray();
		int i = 0;
		while (i < chars.length) {
			int width = widths[chars[i] - 'a'];
			if (col + width > 100) {
				row += 1;
				col = width;
			} else {
				col += width;
			}
			i++;
		}
		return new int[] { row, col };
	}
    
    /**
     * 682. 棒球比赛
     * 
     * 你现在是棒球比赛记录员。
     * 给定一个字符串列表，每个字符串可以是以下四种类型之一：
     * 1.整数（一轮的得分）：直接表示您在本轮中获得的积分数。
     * 2. "+"（一轮的得分）：表示本轮获得的得分是前两轮有效 回合得分的总和。
     * 3. "D"（一轮的得分）：表示本轮获得的得分是前一轮有效 回合得分的两倍。
     * 4. "C"（一个操作，这不是一个回合的分数）：表示您获得的最后一个有效 回合的分数是无效的，应该被移除。
     * 
     * 每一轮的操作都是永久性的，可能会对前一轮和后一轮产生影响。
     * 你需要返回你在所有回合中得分的总和。
     * 
     * 示例 1:
     * 
     * 输入: ["5","2","C","D","+"]
     * 输出: 30
     * 解释: 
     * 第1轮：你可以得到5分。总和是：5。
     * 第2轮：你可以得到2分。总和是：7。
     * 操作1：第2轮的数据无效。总和是：5。
     * 第3轮：你可以得到10分（第2轮的数据已被删除）。总数是：15。
     * 第4轮：你可以得到5 + 10 = 15分。总数是：30。
     * 示例 2:
     * 
     * 输入: ["5","-2","4","C","D","9","+","+"]
     * 输出: 27
     * 解释: 
     * 第1轮：你可以得到5分。总和是：5。
     * 第2轮：你可以得到-2分。总数是：3。
     * 第3轮：你可以得到4分。总和是：7。
     * 操作1：第3轮的数据无效。总数是：3。
     * 第4轮：你可以得到-4分（第三轮的数据已被删除）。总和是：-1。
     * 第5轮：你可以得到9分。总数是：8。
     * 第6轮：你可以得到-4 + 9 = 5分。总数是13。
     * 第7轮：你可以得到9 + 5 = 14分。总数是27。
     * 注意：
     * 
     * 输入列表的大小将介于1和1000之间。
     * 列表中的每个整数都将介于-30000和30000之间。
     * @param ops
     * @return
     */
	public int calPoints(String[] ops) {
		int len = ops.length;
		int idx = 0;
		int[] nums = new int[len];
		for (String op : ops) {
			if ("C".equals(op)) {
				idx--;
				continue;
			}
			if ("D".equals(op)) {
				nums[idx] = nums[idx - 1] * 2;
			} else if ("+".equals(op)) {
				nums[idx] = nums[idx - 1] + nums[idx - 2];
			} else {
				nums[idx] = Integer.parseInt(op);
			}
			idx++;
		}
		// sum
		int sum = 0;
		for (int i = 0; i < idx; i++) {
			sum += nums[i];
		}
		return sum;
	}
    
    /**
     * 575. 分糖果
     * 
     * 给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。
     * 
     * 示例 1:
     * 
     * 输入: candies = [1,1,2,2,3,3]
     * 输出: 3
     * 解析: 一共有三种种类的糖果，每一种都有两个。
     *      最优分配方案：妹妹获得[1,2,3],弟弟也获得[1,2,3]。这样使妹妹获得糖果的种类数最多。
     * 示例 2 :
     * 
     * 输入: candies = [1,1,2,3]
     * 输出: 2
     * 解析: 妹妹获得糖果[2,3],弟弟获得糖果[1,1]，妹妹有两种不同的糖果，弟弟只有一种。这样使得妹妹可以获得的糖果种类数最多。
     * 注意:
     * 
     * 数组的长度为[2, 10,000]，并且确定为偶数。
     * 数组中数字的大小在范围[-100,000, 100,000]内。
     * @param candies
     * @return
     */
	public int distributeCandies(int[] candies) {
		// Math.min(糖果的种类数, 糖果数/2)
		int len = candies.length;
		int[] species = new int[len];
		int idx = 0;
		outer: for (int i = 0; i < len; i++) {
			for (int j = idx - 1; j >= 0; j--) {
				if (species[j] == candies[i]) {
					continue outer;
				}
			}
			species[idx] = candies[i];
			idx++;
		}
		return Math.min(idx, len / 2);
	}
}
